package q340_lengthOfLongestSubstringKDistinct;

import java.util.Collections;
import java.util.HashMap;

public class Solution_1 {
    /*
    用159题的模版 几乎一样即可解滑动窗口题
    但此时出现一个问题 25行的Collections.min方法要遍历map中的value 降低了效率 因此出现solution2
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length();
        if (n * k == 0) return 0;

        int left = 0;
        int right = 0;
        HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();

        int max_len = 1;

        while (right < n) {
            hashmap.put(s.charAt(right), right++);

            if (hashmap.size() == k + 1) {
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                left = del_idx + 1;
            }

            max_len = Math.max(max_len, right - left);
        }
        return max_len;
    }

}
